package com.xiaotao.learn.algorithm.backtrack;

import java.util.LinkedList;
import java.util.List;

class WordSearchSolution {
    String w;
    int line;
    int row;
    char[][] board;
    boolean res = false;
    public boolean exist(char[][] board, String word) {
        w = word;
        line = board.length - 1;
        row = board[0].length - 1;
        this.board = board;

        LinkedList<Integer[]> pos = new LinkedList<>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (word.charAt(0) == board[i][j]) {
                    pos.add(new Integer[]{i, j});
                }
            }
        }
        for (Integer[] start : pos) {
            boolean[][] visited = new boolean[board.length][board[0].length];
            System.out.println("==== begin ====");
            find(start[0], start[1], 0, visited);
        }
        return res;
    }

    public void find(int l, int r, int index, boolean[][] visited) {
        if (res || l > line || l < 0 || r > row || r < 0 || visited[l][r]) {
            return;
        }
        System.out.print(" check " + l + " " + r + " => " + board[l][r] );
        if( board[l][r] == w.charAt(index) ) {
            int next = index + 1;
            if (next == w.length()) res = true;
            System.out.println(" find，index =" + index);
            visited[l][r] = true;
            find(l, r + 1, next, visited);
            find(l, r - 1, next, visited);
            find(l + 1, r, next, visited);
            find(l - 1, r, next, visited);
            visited[l][r] = false;
        } else {
            System.out.println(" false ");
        }
    }
}
/**
 * https://leetcode-cn.com/problems/word-search/
 */
public class WordSearch {
    public static void main(String[] args) {
        WordSearchSolution solution = new WordSearchSolution();
        char[][] input = new char[][] {
                {'A', 'B', 'C', 'E'},
                {'S', 'F', 'E', 'S'},
                {'A', 'D', 'E', 'E'}
        };
        boolean r = solution.exist(input, "ABCESEEEFS");
        System.out.println(r);
    }
}
